{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Most Profit Assigning Work"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #greedy #array #two-pointers #binary-search #sorting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #贪心 #数组 #双指针 #二分查找 #排序"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxProfitAssignment"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #安排工作以达到最大收益"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你有 <code>n</code>&nbsp;个工作和 <code>m</code> 个工人。给定三个数组：&nbsp;<code>difficulty</code>,&nbsp;<code>profit</code>&nbsp;和&nbsp;<code>worker</code>&nbsp;，其中:</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>difficulty[i]</code>&nbsp;表示第 <code>i</code> 个工作的难度，<code>profit[i]</code> 表示第 <code>i</code> 个工作的收益。</li>\n",
    "\t<li><code>worker[i]</code> 是第 <code>i</code> 个工人的能力，即该工人只能完成难度小于等于 <code>worker[i]</code> 的工作。</li>\n",
    "</ul>\n",
    "\n",
    "<p>每个工人&nbsp;<strong>最多</strong> 只能安排 <strong>一个</strong> 工作，但是一个工作可以 <strong>完成多次</strong> 。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子，如果 3 个工人都尝试完成一份报酬为 <code>$1</code> 的同样工作，那么总收益为 <code>$3</code>&nbsp;。如果一个工人不能完成任何工作，他的收益为 <code>$0</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回 <em>在把工人分配到工作岗位后，我们所能获得的最大利润&nbsp;</em>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>difficulty = [2,4,6,8,10], profit = [10,20,30,40,50], worker = [4,5,6,7]\n",
    "<strong>输出: </strong>100 \n",
    "<strong>解释: </strong>工人被分配的工作难度是 [4,4,6,6] ，分别获得 [20,20,30,30] 的收益。</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> difficulty = [85,47,57], profit = [24,66,99], worker = [40,25,25]\n",
    "<strong>输出:</strong> 0</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == difficulty.length</code></li>\n",
    "\t<li><code>n == profit.length</code></li>\n",
    "\t<li><code>m == worker.length</code></li>\n",
    "\t<li><code>1 &lt;= n, m &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>1 &lt;= difficulty[i], profit[i], worker[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [most-profit-assigning-work](https://leetcode.cn/problems/most-profit-assigning-work/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [most-profit-assigning-work](https://leetcode.cn/problems/most-profit-assigning-work/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[2,4,6,8,10]\\n[10,20,30,40,50]\\n[4,5,6,7]', '[85,47,57]\\n[24,66,99]\\n[40,25,25]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        ans=0\n",
    "        worker = sorted(worker)\n",
    "        works = sorted(zip(difficulty,profit),key=lambda x: (x[0],x[1]))\n",
    "        i=j=0\n",
    "        option=None\n",
    "        while i <len(worker):\n",
    "            if j<=len(difficulty)-1 and works[j][0]<=worker[i]:\n",
    "                if not option or option[1]<=works[j][1]:\n",
    "                    option = works[j]\n",
    "                j+=1\n",
    "            if j==len(difficulty) or works[j][0]>worker[i]:\n",
    "                if option: \n",
    "                    ans+=option[1]\n",
    "                i+=1\n",
    "        return ans\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        jobs = sorted([a, b] for a, b in zip(difficulty, profit))\n",
    "        curMax, i = 0, 0\n",
    "        res = 0\n",
    "        for w in sorted(worker):\n",
    "            while i < len(jobs) and w >= jobs[i][0]:\n",
    "                curMax = max(curMax, jobs[i][1])\n",
    "                i += 1\n",
    "            res += curMax\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        jobs = sorted([a, b] for a, b in zip(difficulty, profit))\n",
    "        curMax, i = 0, 0\n",
    "        res = 0\n",
    "        for w in sorted(worker):\n",
    "            while i < len(jobs) and w >= jobs[i][0]:\n",
    "                curMax = max(curMax, jobs[i][1])\n",
    "                i += 1\n",
    "            res += curMax\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        \n",
    "        z=zip(profit,difficulty)\n",
    "        profit=sorted(list(z))\n",
    "        worker=sorted(worker)\n",
    "        \n",
    "        d=0\n",
    "        flag1=len(difficulty)-1\n",
    "        flag2=len(worker)-1\n",
    "        while flag2*flag1>=0:#任何列表为空才停止\n",
    "            if profit[flag1][-1]>worker[flag2]:\n",
    "                flag1-=1\n",
    "            else:\n",
    "                d+=profit[flag1][0]\n",
    "                flag2-=1\n",
    "            if flag1<0 or flag2<0:\n",
    "                break\n",
    "        return d\n",
    "                    \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        idx = sorted(range(len(profit)), key = lambda x: difficulty[x])\n",
    "        dp = {}\n",
    "        maxp = 0\n",
    "        for i in idx:\n",
    "            maxp = max(maxp, profit[i])\n",
    "            dp[difficulty[i]] = maxp\n",
    "            \n",
    "        ds = sorted(dp.keys())\n",
    "        \n",
    "        ans = 0\n",
    "        for i in worker:\n",
    "            if i < ds[0]:\n",
    "                continue\n",
    "            l = 0\n",
    "            r = len(ds)-1\n",
    "            while l < r:\n",
    "                mid = (l+r+1)//2\n",
    "                if ds[mid] > i:\n",
    "                    r = mid - 1\n",
    "                else:\n",
    "                    l = mid\n",
    "            # print(i, ds[l])\n",
    "            ans += dp[ds[l]]\n",
    "\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        dic = {}\n",
    "        for i in range(len(profit)):\n",
    "            if difficulty[i] in dic.keys():\n",
    "                dic[difficulty[i]] = max(dic[difficulty[i]], profit[i])\n",
    "            else:\n",
    "                dic[difficulty[i]] = profit[i]\n",
    "        dic = sorted(dic.items(), key=lambda d:d[0])\n",
    "        true_dic = []\n",
    "        min_x = 0\n",
    "        for d in dic:\n",
    "            if d[1] > min_x:\n",
    "                true_dic.append(d)\n",
    "                min_x = d[1]\n",
    "        \n",
    "        sum = 0\n",
    "        true_dic.reverse()\n",
    "        for work in worker:\n",
    "            for e in true_dic:\n",
    "                if work >= e[0]:\n",
    "                    sum += e[1]\n",
    "                    break\n",
    "        return sum"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import Counter\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        \"\"\"\n",
    "        :type difficulty: List[int]\n",
    "        :type profit: List[int]\n",
    "        :type worker: List[int]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        li = sorted(zip(profit,difficulty))\n",
    "        ret = 0\n",
    "        worker = Counter(worker)\n",
    "        for i in sorted(worker,reverse=True):\n",
    "            while li and li[-1][1]>i:\n",
    "                li.pop()\n",
    "            if li:\n",
    "                ret+=li[-1][0]*worker[i]\n",
    "            else:\n",
    "                break\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        worker.sort();\n",
    "        Lw=len(worker);\n",
    "        L=len(difficulty);\n",
    "        idx=list(range(L));\n",
    "        idx.sort(key=lambda x:difficulty[x]);\n",
    "        pronew=[profit[i] for i in idx];\n",
    "        w_idx,d_idx=0,0;\n",
    "        rlt=0;\n",
    "        ProCmp=-1;\n",
    "        tmp=-1;\n",
    "        while w_idx<Lw and d_idx<L:\n",
    "            if difficulty[idx[d_idx]]<=worker[w_idx]:\n",
    "\n",
    "                #if d_idx<L:\n",
    "                tmp=max(tmp,pronew[d_idx]);\n",
    "                d_idx+=1;\n",
    "            else:\n",
    "                if d_idx!=0 and difficulty[idx[d_idx-1]]<=worker[w_idx]:\n",
    "                    d_idx-=1;\n",
    "                    rlt+=tmp#rlt+=pronew[d_idx];\n",
    "                w_idx+=1;\n",
    "        if w_idx>=Lw:\n",
    "            return rlt;\n",
    "        else:\n",
    "            if difficulty[idx[-1]]<=worker[w_idx]:\n",
    "                return rlt+(Lw-w_idx)*tmp#return rlt+(Lw-w_idx)*pronew[-1];\n",
    "            else:\n",
    "                return rlt\n",
    "            \n",
    "                \n",
    "                \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# sort worker from small to large\n",
    "# sort (difficulty, profit) tasks\n",
    "# workp = 0 --> sorted worker array, taskp = 0--> sorted task array\n",
    "# maxprofit : record max profit \n",
    "# O(nlogn + klogk)\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        worker = sorted(worker)\n",
    "        task = sorted(range(len(profit)), key=lambda i: difficulty[i])\n",
    "        taskp = 0\n",
    "        maxprofit = 0\n",
    "        res = 0\n",
    "        for w in worker:\n",
    "            while taskp < len(task) and difficulty[task[taskp]] <= w:\n",
    "                maxprofit = max(maxprofit, profit[task[taskp]])\n",
    "                taskp += 1\n",
    "            res += maxprofit\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        worker.sort(reverse=True)\n",
    "\n",
    "        idx = [i for i in range(len(difficulty))]\n",
    "        idx.sort(key=lambda x:profit[x], reverse=True)\n",
    "\n",
    "        res = 0\n",
    "        p_w = 0\n",
    "        p_i = 0\n",
    "\n",
    "        while p_i < len(difficulty) and p_w < len(worker):\n",
    "            if difficulty[idx[p_i]] <= worker[p_w]:\n",
    "                res += profit[idx[p_i]]\n",
    "                p_w += 1\n",
    "            else:\n",
    "                p_i += 1\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        vec = sorted((d,p) for d,p in zip(difficulty,profit))\n",
    "        worker.sort()\n",
    "        #print(\"worker={}\".format(worker))\n",
    "        #print(\"vec={}\".format(vec))\n",
    "        left=right=res = 0\n",
    "        for i in range(len(worker)):\n",
    "            #cd = worker[i]\n",
    "            while right<len(vec) and vec[right][0]<=worker[i]:\n",
    "               left = max(left,vec[right][1])\n",
    "               right+=1\n",
    "            res+=left\n",
    "        return res\n",
    "            \n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import random\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker) -> int:\n",
    "        # 按 profit 排序\n",
    "        def partition(nums, additions, l, r):\n",
    "            pivot = random.randint(l, r)\n",
    "            nums[pivot], nums[r] = nums[r], nums[pivot]\n",
    "            additions[pivot], additions[r] = additions[r], additions[pivot]\n",
    "            i = l\n",
    "            for j in range(l, r):\n",
    "                if nums[j] > nums[r]:\n",
    "                    nums[j], nums[i] = nums[i], nums[j]\n",
    "                    additions[j], additions[i] = additions[i], additions[j]\n",
    "                    i += 1\n",
    "            nums[i], nums[r] = nums[r], nums[i]\n",
    "            additions[i], additions[r] = additions[r], additions[i]\n",
    "            return i\n",
    "\n",
    "        def quicksort(nums, additions, l, r):\n",
    "            if l >= r:\n",
    "                return\n",
    "            pivot = partition(nums, additions, l, r)\n",
    "            quicksort(nums, additions, l, pivot - 1)\n",
    "            quicksort(nums, additions, pivot + 1, r)\n",
    "\n",
    "        works = len(difficulty)\n",
    "        quicksort(profit, difficulty, 0, works - 1)\n",
    "        list.sort(worker)\n",
    "        worker.reverse()\n",
    "        total_profits = 0\n",
    "        pre = 0\n",
    "        for w in worker:\n",
    "            for i in range(pre, works):\n",
    "                if w >= difficulty[i]:\n",
    "                    total_profits += profit[i]\n",
    "                    break\n",
    "            pre = i\n",
    "        return total_profits"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        job_num = len(difficulty)\n",
    "        j_idx = list(range(len(difficulty)))\n",
    "        j_idx.sort(key=lambda i:difficulty[i])\n",
    "        worker.sort()\n",
    "\n",
    "\n",
    "        curd = 0\n",
    "        curp = 0\n",
    "        i = 0\n",
    "        ans = 0\n",
    "        for w in worker:\n",
    "            while i < job_num:\n",
    "                nextd = difficulty[j_idx[i]]\n",
    "                nextp = profit[j_idx[i]]\n",
    "                if nextd > w:\n",
    "                    break\n",
    "                curd = nextd\n",
    "                curp = max(curp, nextp)\n",
    "                i += 1\n",
    "            ans += curp\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        diff = sorted(map(tuple,zip(difficulty,profit)))\n",
    "        worker.sort()\n",
    "        res = maxpro = j=0\n",
    "        for i in worker:\n",
    "            while j<len(diff) and diff[j][0]<=i:\n",
    "                maxpro = max(maxpro,diff[j][1])\n",
    "                j+=1\n",
    "            res +=maxpro\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        jobs = list(zip(difficulty, profit))\n",
    "        jobs.sort()\n",
    "        ans = i = best = 0\n",
    "        for skill in sorted(worker):\n",
    "            while i < len(jobs) and skill >= jobs[i][0]:\n",
    "                best = max(best, jobs[i][1])\n",
    "                i += 1\n",
    "            ans += best\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        jobs = list(zip(difficulty, profit))\n",
    "        jobs.sort(key = lambda x:x[0])\n",
    "        ans = i = best = 0\n",
    "        for skill in sorted(worker):\n",
    "            while i < len(jobs) and skill >= jobs[i][0]:\n",
    "                best = max(best, jobs[i][1])\n",
    "                i += 1\n",
    "            ans += best\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def find_p(self, val):\n",
    "        if val < self.dp[0][0]: return 0\n",
    "        low = 0; high = len(self.dp) - 1\n",
    "\n",
    "        while low < high:\n",
    "            mid = (low + high + 1) // 2\n",
    "            if self.dp[mid][0] > val:\n",
    "                high = mid - 1\n",
    "            elif self.dp[mid][0] < val:\n",
    "                low = mid\n",
    "            else:\n",
    "                low = mid\n",
    "                break\n",
    "        return self.dp[low][1]\n",
    "\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        if not worker: return 0\n",
    "        self.dp = []\n",
    "        for idx, val1 in enumerate(difficulty):\n",
    "            self.dp.append([val1, profit[idx]])\n",
    "        \n",
    "        self.dp.sort(key = lambda x: (x[0], -x[1]))\n",
    "\n",
    "        maxv = 0\n",
    "        for idx, val_list in enumerate(self.dp):\n",
    "            self.dp[idx][1] = max(maxv, val_list[1])\n",
    "            maxv = self.dp[idx][1]\n",
    "            \n",
    "        ans = 0\n",
    "        for val in worker:\n",
    "            ans += self.find_p(val)\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        n=len(difficulty)\n",
    "        profit=[profit[i] for i in sorted(range(n),key=lambda x:difficulty[x])]\n",
    "        difficulty.sort()\n",
    "        # 根据难度排序\n",
    "        preMax=[0]\n",
    "        for p in profit:\n",
    "            preMax.append(max(p,preMax[-1]))\n",
    "        # 每个难度对应的最大利润，防止高难度工作却赚的少\n",
    "        ans=0\n",
    "        for w in worker:\n",
    "            i = bisect.bisect_right(difficulty, w)\n",
    "            # i为该工人能做的最难工作的下标\n",
    "            if i < n and difficulty[i] == w: i+=1\n",
    "            ans += preMax[i]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        res = 0\n",
    "        m_dict = {}\n",
    "        for i in range(len(difficulty)):\n",
    "            if difficulty[i] not in m_dict:\n",
    "                m_dict[difficulty[i]] = profit[i]\n",
    "            else:\n",
    "                m_dict[difficulty[i]] = max(profit[i], m_dict[difficulty[i]])\n",
    "        difficulty.sort()\n",
    "        temp = 0\n",
    "        for d in difficulty:\n",
    "            temp = max(m_dict[d], temp)\n",
    "            m_dict[d] = temp\n",
    "        for i in range(len(worker)):\n",
    "            index = bisect_right(difficulty, worker[i]) - 1\n",
    "            if index >= 0:\n",
    "                res += m_dict[difficulty[index]]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        sorted_worker = sorted(worker,reverse = True)\n",
    "        sorted_profit = sorted(profit,reverse = True)\n",
    "        profit_dict = {}\n",
    "        for pro,diff in zip(profit,difficulty):\n",
    "            if pro not in profit_dict or profit_dict[pro] > diff:\n",
    "                profit_dict[pro] = diff\n",
    "        ans = 0\n",
    "        i = 0\n",
    "        for profit in sorted_profit:\n",
    "            while i < len(sorted_worker):\n",
    "                if profit_dict[profit] <= sorted_worker[i]:\n",
    "                    ans += profit\n",
    "                    i += 1\n",
    "                else:\n",
    "                    break\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        index = sorted(range(len(difficulty)), key=lambda x: difficulty[x])\n",
    "        jobs = [(0, 0)]\n",
    "        for i in index:\n",
    "            if profit[i] > jobs[-1][1]:\n",
    "                jobs.append((difficulty[i], profit[i]))\n",
    "        \n",
    "        result = 0\n",
    "        for w in worker:\n",
    "            i = bisect_right(jobs, (w,inf)) - 1\n",
    "            result += jobs[i][1]\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 二分找左边界\n",
    "def leftBound(a: List[int], t: int) -> int:\n",
    "    l, r = 0, len(a) - 1\n",
    "    while l < r:\n",
    "        mid = (l + r + 1) >> 1\n",
    "        if a[mid] > t:\n",
    "            r = mid - 1\n",
    "        else:\n",
    "            l = mid\n",
    "    return -1 if a[l] > t else l\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "        排序 + 二分\n",
    "    '''\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        n = len(difficulty)\n",
    "        idx = [0] * n\n",
    "        for i in range(n):\n",
    "            idx[i] = i\n",
    "        idx.sort(key=lambda x: difficulty[x])\n",
    "        difficulty.sort()\n",
    "        max_profit = [0] * n             # 预处理max_profit数组，维护当前i的最大报酬\n",
    "        max_profit[0] = profit[idx[0]]\n",
    "        for i in range(1, n):\n",
    "            j = idx[i]\n",
    "            max_profit[i] = max(max_profit[i - 1], profit[j])         \n",
    "        ans = 0\n",
    "        for w in worker:\n",
    "            index = leftBound(difficulty, w)\n",
    "            if index == -1: continue\n",
    "            ans += max_profit[index]\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        dic = {}\n",
    "        n = len(profit)\n",
    "        for i in range(n):\n",
    "            prof = profit[i]\n",
    "            if prof not in dic or difficulty[i] < dic[prof]:\n",
    "                dic[profit[i]] = difficulty[i]\n",
    "        \n",
    "        profit.sort(reverse = True)\n",
    "        worker.sort(reverse = True)\n",
    "\n",
    "        res = 0\n",
    "        w = 0\n",
    "        nn = len(worker)\n",
    "        for i in range(n):\n",
    "            prof = profit[i]\n",
    "            while w < nn:\n",
    "                if worker[w] >= dic[prof]:\n",
    "                    res += prof\n",
    "                    w += 1\n",
    "                else:\n",
    "                    break\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "\n",
    "        \n",
    "        \n",
    "        n = len(difficulty)\n",
    "        \n",
    "        indexes = [i for i in range(n)]\n",
    "        indexes = sorted(indexes, key=lambda x:difficulty[x])\n",
    "        difficulty = [difficulty[i] for i in indexes]\n",
    "        profit = [profit[i] for i in indexes]\n",
    "\n",
    "        #print(difficulty)\n",
    "        #print(profit)\n",
    "\n",
    "        dp = [0]*n \n",
    "        dp[0] = profit[0]\n",
    "        for i in range(1,n):\n",
    "            dp[i] = max(profit[i],dp[i-1])\n",
    "        \n",
    "        #print(dp)\n",
    "        ans = 0 \n",
    "        for w in worker:\n",
    "            index = bisect.bisect_right(difficulty, w)\n",
    "            if index==0:\n",
    "                continue \n",
    "            else:\n",
    "                ans += dp[index-1]\n",
    "        return ans \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        jobs = list(zip(difficulty, profit))\n",
    "        jobs.sort()\n",
    "        worker.sort()\n",
    "        i, best, ans = 0, 0, 0\n",
    "        # print(f\"jobs:{jobs}, worker:{worker}\")\n",
    "        for w in worker:\n",
    "            while i < len(difficulty) and w >= jobs[i][0]: # 维护最小难度到当前难度的最大收益\n",
    "                best = max(best, jobs[i][1])\n",
    "                i += 1\n",
    "            ans += best\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def maxProfitAssignment(self, difficulty, profit, worker):\n",
    "        n = len(difficulty)\n",
    "        jobs = [[difficulty[i],profit[i]] for i in range(n) ]\n",
    "        jobs.sort()\n",
    "        ans = i = best = 0\n",
    "        for skill in sorted(worker):\n",
    "            while i < len(jobs) and skill >= jobs[i][0]:\n",
    "                best = max(best, jobs[i][1])\n",
    "                i += 1\n",
    "            ans += best\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        work_tuples = sorted(zip(difficulty, profit), key=lambda s: s[0])\n",
    "        worker.sort(key=lambda x: - x)\n",
    "        res = 0\n",
    "        stack = []\n",
    "        for i in work_tuples:\n",
    "            if not stack or i[1] > stack[-1][1]:\n",
    "                stack.append(i)\n",
    "        for w in worker:\n",
    "            while stack and stack[-1][0] > w:\n",
    "                stack.pop()\n",
    "            if not stack:\n",
    "                break\n",
    "            res += stack[-1][1]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        work_tuples = sorted(zip(difficulty, profit), key=lambda s : s[0])\n",
    "        profits = [t[1] for t in work_tuples]\n",
    "        worker.sort(key=lambda x: - x)\n",
    "        total_profit = 0\n",
    "        max_profit_dict = {}\n",
    "        for w in worker:\n",
    "            if max_profit_dict.get(w, -1) != -1:\n",
    "                total_profit += max_profit_dict.get(w, -1)\n",
    "                continue\n",
    "            while len(work_tuples) > 0 and w < work_tuples[-1][0]:\n",
    "                work_tuples.pop()\n",
    "                profits.pop()\n",
    "            if len(work_tuples) == 0:\n",
    "                break\n",
    "            p = max(profits)\n",
    "            max_profit_dict[w] = p\n",
    "            total_profit += p\n",
    "        return total_profit\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxProfitAssignment(self, difficulty: List[int], profit: List[int], worker: List[int]) -> int:\n",
    "        def bisect_right(nums, target):\n",
    "            left = 0\n",
    "            right = len(nums)\n",
    "            while left < right:\n",
    "                mid = (left + right) // 2\n",
    "                if nums[mid] <= target:\n",
    "                    left = mid + 1\n",
    "                else:\n",
    "                    right = mid\n",
    "            return left\n",
    "        \n",
    "        \n",
    "        dic = {}\n",
    "        for d, p in zip(difficulty, profit):\n",
    "            if d in dic:\n",
    "                dic[d] = max(dic[d], p)\n",
    "            else:\n",
    "                dic[d] = p\n",
    "        dic2 = dict(sorted(dic.items()))\n",
    "        #print(dic2)\n",
    "        profit = list(dic2.values())\n",
    "        maxprofit = [0] * len(profit)\n",
    "        for i in range(len(profit)):\n",
    "            if i != 0:\n",
    "                maxprofit[i] = max(maxprofit[i - 1], profit[i])\n",
    "            else:\n",
    "                maxprofit[i] = max(maxprofit[i], profit[i])\n",
    "        #maxprofit = [max(profit[:(i + 1)]) for i in range(len(profit))]\n",
    "        #print(maxprofit)\n",
    "        d2 = sorted(list(dic2.keys()))\n",
    "        ans = 0\n",
    "        for w in worker:\n",
    "            pos = bisect_right(d2, w) - 1\n",
    "            if pos < 0:\n",
    "                continue\n",
    "            else:\n",
    "                #print(maxprofit[pos])\n",
    "                ans = ans + maxprofit[pos]\n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
